A computer game often includes a plurality of graphic image backgrounds that portray a virtual world in which objects move in accordance with the machine instructions comprising the game's software. Typically, the movement of at least one of the objects in a displayed image for the computer game is controlled by a user. When a collision event for the moving object is detected, the game reacts to the event in a defined manner. The moving object may, for example, comprise a spaceship firing weapons at attacking invaders or a character jumping about so that falling rocks or other hazards may be avoided. An avatar is another type of object that the user may move in a 3D virtual world environment (VWE), such as a chat room, for interaction with other avatars controlled by other users. In each of these examples, any time the moving object collides with any other object in a virtual world or gaming environment, it may be necessary to detect the collision event so that a predefined response or action can be performed.
The computational speed of a single computer that implements a display of a VWE is readily enhanced by increasing the computer's hardware resources, such as increasing memory and/or processor speed, so that collisions between objects in the environment may be detected in real time. Unlike a VWE that is solely implemented by a single computer, graphic images in a networked VWE are simultaneously implemented on a plurality of computers for display to multiple users. Although, the Internet network provides a relatively slow communication path between networked computers, it is a popular medium to interconnect computers that simultaneously display a virtual world to enable a number of users to interact. In a networked virtual world, the detection of collisions between moving objects is not as readily optimized with hardware enhancements because of the inherent latency of communications over the network. It is thus important for a collision detection technique in a networked VWE to be relatively computationally efficient so that between interconnected computers, unacceptably long delays in detecting and responding to a collision event may be avoided.
The projection of the path of a moving 3D object onto a two-dimensional (2D) surface is a well known geometric technique that is commonly performed prior to determining if an object has collided with another object, so that the number of computations necessary to detect a collision is reduced. In one prior art technique described by Antonio in "Graphics Gems III," the projected image of each object on the 2D surface is bounded by a series of straight line segments, and another straight line segment is projected onto the 2D surface along the path that the moving object is traveling. Significantly, Antonio treats each line segment that bounds the image of the object as a separate entity. At predefined intervals of time, computations are made for each line segment surrounding an object to determine if the line segment defining the path of the moving object has intersected the computed line segment. If a collision occurs between the selected time intervals at which the check is made, the collision will not be detected. Also, the two special cases of a path line segment overlaying an object line segment or the path line segment intersecting the vertex between two consecutive object line segments are not considered by this prior art technique. Moreover, Antonio's technique requires at least six multiplicative steps each time it is employed. Thus, Antonio's technique for detecting collisions between objects is too unreliable, and requires too many computations (six multiplication steps) to be usable in a networked 3D VWE.
In another prior art technique, the special case of a moving object that collides with a corner (vertex) formed by the two endpoints of two sequential line segments that encircle an object's projection into 2D space is solved. However, the solution is inefficient because each endpoint that forms the vertex is separately calculated. Significantly, two floating point calculations performed by a computer for the same nominal position (vertex) in a 3D VWE may provide two slightly different values due to rounding. These rounding differences can cause problems in handling collisions. For example, in the popular 3D computer game "Doom" by ID Software, Inc., when a player's character collides with a corner formed by two walls, the character sometimes slips through a "crack" at the corner formed by the walls. The crack is created by a difference in the two floating point calculations determined for the individual endpoints of the two line segments (walls) that form the corner. At corners, Doom determines if a collision between the center point of the moving character and the first wall has occurred, which includes determining the value of the vertex formed by a first endpoint and a second endpoint at the corner. If a collision is not detected, Doom next determines if the center point has collided with the second wall, again determining the value of the vertex formed by the first and second endpoints. Since the same vertex formed by the two endpoints is calculated twice, slight differences in the two calculated values can create a crack that allows the center point of the moving object to pass through and crash the game's software. Although Doom's detection of collisions between moving objects is computationally efficient, this prior art solution is not sufficiently robust for reliable implementation in a networked VWE.
In summary, prior art collision detection techniques are unsuitable for use in a networked 3D VWE. Accordingly, an approach is required that reduces the number of computations necessary to detect collisions between objects, implicitly handles special case conditions, and detects collisions whenever they may occur in a frame rendering time interval.